import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2025-10-28
 * Time: 10:59
 */
class Solution1{
    public int findKthLargest(int[] nums, int k){
        return qsort(nums, 0, nums.length-1, k);
    }

    public int qsort(int[] nums, int l, int r, int k){
        //l > r
        if(l == r) return nums[l];

        //1.随机选一个基准元素
        int key = nums[new Random().nextInt(r - l +1) + l];

        //2.根据基准元素，把数组分成三块
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(nums[i]  < key) swap(nums, ++left, i++);
            else if(nums[i] == key) i++;
            else swap(nums, --right, i);
        }

        //3.分类讨论
        int b = right - left - 1, c = r - right + 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }


    public void swap(int[] nums, int left, int right){
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;
    }
}




public class demo1 {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        int[] nums = {1,2,3,4,5,6,7};

        System.out.println(solution.findKthLargest(nums, 5));
    }
}
